package linkedlist;

import org.junit.Test;

import static linkedlist.ListNode.buildList;
import static linkedlist.ListNode.printList;

public class ReverseLinkedListii92 {
    @Test
    public void test() {
        ListNode list = buildList(1, 2, 3, 4, 5);
        printList(list, "origin");
        printList(reverseBetween(list, 2, 4), "reversed");

        list = buildList(5);
        printList(list, "origin");
        printList(reverseBetween(list, 1, 1), "reversed");
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        int i = 1;
        ListNode prev = null;
        ListNode curr = head;

        while (i < left) {
            prev = curr;
            curr = curr.next;
            i++;
        }

        // 记录下翻转的起始节点及前驱
        ListNode prevStart = prev;
        ListNode start = curr;

        // 四步曲
        while (i <= right) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            i++; // 别忘了
        }

        // start变成了翻转段的最后一个, 需要接上后面的
        start.next = curr;

        // prev现在是翻转段的头, 需要跟prevStart衔接上
        if (prevStart != null) {
            prevStart.next = prev;
        }

        // 需要判断是否从head开始翻转
        return left == 1 ? prev : head;
    }
}
